
// Copyright (C) 2007 Richard Uhler
// This file is part of Esiply.
//
// Esiply is free software; you can redistribute it and/or modify
// it under the terms of the GNU General Public License, Version 2,
// as published by the Free Software Foundation.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program.  If not, see <http://www.gnu.org/licenses/>.

// This is the implementation of javascript Regular Expressions.

// TODO: The internal stuff shouldn't be polluting the global space!

var Token = function(type, value)
{
    this.type = type;
    this.value = value;
};
Token.prototype.valueOf = function()
{
    return this.type + "(" + this.value + ")";
};

// Terminals
Token.END = "END";
Token.ERROR = "ERROR";
Token.BAR = "|";
Token.PATTERN_CHARACTER = "PATTERN_CHARACTER";

// Nonterminals
Token.PATTERN = "PATTERN";
Token.DISJUNCTION = "DISJUNCTION";
Token.ALTERNATIVE = "ALTERNATIVE";
Token.TERM = "TERM";
Token.ATOM = "ATOM";
Token.ACCEPTED = "ACCEPTED";

// A Lexer is our lexegraphical scanner. It turns the regular expression
// string into a series of tokens. It takes an input string, and on each
// call to next(), returns the next token. When it gets to the end
// it continually returns the END token.
var Lexer = function(input)
{
    this.input = new String(input);
    this.pos = 0;
};

Lexer.isPatternChar = function(char)
{
    // TODO: don't just return true
    // I'm doing this now so I can hopefully get by on mozilla test
    // suite when it tries /\(\)$/ in ecma_3/shell.js, which is 
    // botching a bunch of tests which otherwise would be useful.
    return true;
    switch (char)
    {
        case "^": return false;
        case "$": return false;
        // TODO: this is due to a bug in the scanner which doesn't
        // let me have "\\" for some reason. FIX IT!
        case "a\\a".charAt(1): return false;
        case ".": return false;
        case "*": return false;
        case "+": return false;
        case "?": return false;
        case "(": return false;
        case ")": return false;
        case "[": return false;
        case "]": return false;
        case "{": return false;
        case "}": return false;
        case "|": return false;
        default: return true;
    }
};

Lexer.prototype.next = function()
{
    if (this.pos >= this.input.length)
    {
        return new Token(Token.END);
    }
    else if (this.input.charAt(this.pos) == "|")
    {
        this.pos++;
        return new Token(Token.BAR);
    }
    else if (Lexer.isPatternChar(this.input.charAt(this.pos)))
    {
        return new Token(Token.PATTERN_CHARACTER, this.input.charAt(this.pos++));
    }
    this.pos++;
    return new Token(Token.ERROR);
};

StackNode = function(state, value)
{
    this.state = state;
    this.value = value;
};

StackNode.prototype.valueOf = function()
{
    return "(" + this.state + ", " + this.value + ")";
};

Stack = function()
{
    this.data = [];
};

Stack.prototype.push = function(val)
{
    this.data.push(val);
};

Stack.prototype.pop = function()
{
    this.data.pop();
};

Stack.prototype.top = function()
{
    return this.data[this.data.length-1];
};

Parser = function(lexer)
{
    this.lexer = lexer;
    this.stack = new Stack();
    this.stack.push(new StackNode(Parser.initial, 0));
    this.next = lexer.next();
    debug("parse: initial token: " + this.next + "\n");
};

Parser.prototype.parse = function()
{
    debug("parse: enter\n");
    while (true)
    {
        // Check to see if we are done
        if (this.stack.top().state.accepted)
        {
            debug("parse: accepted\n");
            return this.stack.top().value;
        }
        else if (this.next.type in this.stack.top().state)
        {
            // Shift in the token
            debug("parse: shift: " + this.next + "\n");
            this.stack.push(new StackNode(this.stack.top().state[this.next.type], this.next.value));
            this.next = this.lexer.next();
        }
        else if ("def" in this.stack.top().state)
        {
            // Reduce using the default rule
            debug("parse: reduce with: " + this.stack.top().state.def + "\n");
            var tok = this[this.stack.top().state.def]();
            debug("parse: reduced to: " + tok + "\n");
            var newnode = new StackNode(this.stack.top().state[tok.type], tok.value);
            this.stack.push(newnode);
        }
        else
        {
            debug("Syntax error at token: " + this.next + "\n");
            return;
        }
    }
};

// The States.
// For any terminals the state can transition from we will have an entry
// in the state whose proeprty name is the terminal, and whose value is the
// next state to go into after shifting the terminal onto the stack.
//
// If the terminal fails, we have a "def" property whose value is a string
// which is a Parser.prototype property whose value is a function
// which reduces appropriately. The this value to that function is the parser.
//
// For any nonterminals, we have a property with the name of the non-terminal,
// and value is the state we should go to having just reduced to that
// terminal.

// Declarations of states.
// The numbers indicate which states they are in research/regex.output
// The state numbers will change with any updates to the grammar.
Parser.initial = {};                    // 0
Parser.pattern_dot = {};                // 1
Parser.disjunction_dot = {};            // 2
Parser.alternative_dot = {};            // 3
Parser.accepting = {};                  // 4
Parser.pattern_character_dot = {};      // 5
Parser.disj_alt_bar_dot_disj = {};      // 6
Parser.alternative_term_dot = {};       // 7
Parser.atom_dot = {};                   // 8
Parser.disj_alt_bar_disj_dot = {};      // 9
Parser.accepted = {};                   // x

// Definitions of states.
Parser.initial[Token.ACCEPTED] = Parser.accepted;
Parser.initial.def = "red_alternative_empty";
Parser.prototype.red_alternative_empty = function()
{
    // Alternative: /* empty */
    // Ecma 15.10.2.4
    // The production Alternative :: [empty] evalutates by returning a 
    // Matcher that takes two arguments, a State x and a Continuation c,
    // and returns the result of calling c(x)
    var matcher = function(x, c, vars)
    {
        debug("matching alternative :: [empty]\n");
        return c(x, vars);
    };
    return new Token(Token.ALTERNATIVE, matcher);
};
Parser.initial[Token.PATTERN] = Parser.pattern_dot;
Parser.initial[Token.DISJUNCTION] = Parser.disjunction_dot;
Parser.initial[Token.ALTERNATIVE] = Parser.alternative_dot;

Parser.pattern_dot[Token.END] = Parser.accepting;

Parser.disjunction_dot.def = "red_pattern_disjunction";
Parser.prototype.red_pattern_disjunction = function()
{
    // Pattern: Disjunction
    // Ecma 15.10.2.2
    // The production Pattern :: Disjunction evaluates as follows.
    // 1. Evaluate Disjunction to obtain a Matcher m (its on the stack)
    var m = this.stack.top().value;
    this.stack.pop();

    // 2. Return an internal closure that takes two arguments, a string
    // str and an integer index, and performs the following
    var func = function(str, index)
    {
        debug("match: input is:" + str + "\n");
        // 1. Let input be the given string str
        // 2. Let InputLength be the lenght of input
        // TODO: who sets NCapturingParens?
        var vars = {};
        vars.input = str;
        vars.input_length = vars.input.length;
        vars.NCapturingParens = 0;
        vars.ignore_case = this.ignoreCase;
        vars.multiline = this.multiline;

        // 3. Let c be a continuation that always returns its state argument
        // as a successful match result
        var c = function(state, vars)
        {
            return state;
        };

        // 4. let cap be an internal array of NCapturingParens undefined
        // values, indexed 1 through NCapturingParens.
        // indexed 1 through NCapturingParens
        var cap = new Array(vars.NCapturingParens+1); 

        // 5. Let x be the state index, cap
        var x = new State(index, cap);

        // 6. Call m(x,c) and return its results
        debug("matching pattern :: disjunction\n");
        debug("input is:" + vars.input + "\n");
        return m(x,c, vars);
    };
    return new Token(Token.PATTERN, func);
};

Parser.alternative_dot[Token.PATTERN_CHARACTER] = Parser.pattern_character_dot;
Parser.alternative_dot[Token.BAR] = Parser.disj_alt_bar_dot_disj;
Parser.alternative_dot.def = "red_disjunction_alternative";
Parser.prototype.red_disjunction_alternative = function()
{
    // Ecma 15.10.2.3 Disjunction :: Alternative
    // The production Disjunction :: Alternative evalutes by evaluating
    // Alternative to obtain a Match and returning that Matcher.
    // In other words: just return the same value as Alternative
    var value = this.stack.top().value;
    this.stack.pop();
    return new Token(Token.DISJUNCTION, value);
};
Parser.alternative_dot[Token.TERM] = Parser.alternative_term_dot;
Parser.alternative_dot[Token.ATOM] = Parser.atom_dot;

Parser.accepting.def = "red_accept";
Parser.prototype.red_accept = function()
{
    // Pop off this state(end) and the previous(pattern), go to
    // accepted.
    this.stack.pop();
    var value = this.stack.top().value;
    this.stack.pop();
    return new Token(Token.ACCEPTED, value);
};

Parser.pattern_character_dot.def = "red_atom_pattern_char";
Parser.prototype.red_atom_pattern_char = function()
{
    // Atom : PATTERN_CHARACTER
    // Ecma 15.10.2.8 Atom
    // 1. Let ch be the character represented by PatternCharacter
    var ch = this.stack.top().value;
    this.stack.pop();

    // 2. let A be a one-element CharSet containing the character ch
    var a = new CharSet(ch);

    var characterSetMatcher = function(a, invert, vars)
    {
        // Ecma 15.10.2.8
        // 1. return an internal Matcher closure that takes two arguments,
        // a state x and a continuation c, and performs the following:
        var matcher = function(x, com, vars)
        {
            // 1. Let e be x's endIndex
            var e = x.endIndex;

            // 2. if e == inputLength, return failure
            if (e == vars.input_length)
            {
                debug("charSetMatcher: e is inputlength\n");
                return State.FAILURE;
            }

            // 3. let c be the character input[e]
            var c = vars.input.charAt(e);
            debug("charSetMatcher: attempting to match: " + c  + "\n");
            debug("( from input: " + vars.input + ")\n");
            debug("( from vars; " + vars.toString() + ")\n");

            // 4. let cc be the result of Canonicalize(c)
            var canonicalize = function(ch, vars)
            {
                // 1. if IgnoreCase is false, return ch
                if (!vars.ignore_case)
                {
                    debug("canonicalize: ignorecase is false, returning: " + ch + "\n");
                    return ch;
                }

                // 2. Let u be ch converted to upper case as if by calling
                // String.prototype.toUpperCase on the one-character string ch
                var u = ch.toUpperCase();

                // 3. If u does not consist of a single character, return ch
                if (u.length != 1)
                {
                    return ch;
                }

                // 4. let cu be u's character
                var cu = u;

                // 5. If ch's code point value is greater than or equal to
                // 128 and cu's code point value is less than decimal 128,
                // return ch
                if (ch.charCodeAt(0) >= 128 && cu.charCodeAt(0) < 128)
                {
                    return ch;
                }
                return cu;
            };
            var cc = canonicalize(c, vars);

            // 5. if invert is true, go to step 8
            if (invert)
            {
                // 8. If there exists a member a of set A such that
                // canonicalize(a) == cc, then return failure
                for (char in a)
                {
                    if (canonicalize(char, vars) == cc)
                    {
                        return State.FAILURE;
                    }
                }
            }

            // 6. If there does not exist a member of a of set A such that
            // Canonicalize(a) == cc, then return failure
            for_else:
            {
                for (char in a)
                {
                    if (canonicalize(char, vars) == cc)
                    {
                        break for_else;
                    }
                }
                debug("charSetMatcher: no member of A matches: " + cc + "\n");
                return State.FAILURE;
            }

            // 7. go to step 9
            // 9. Let cap be x's captures internal array
            var cap = x.captures;

            // 10. let y be the state (e+1, cap)
            var y = new State(e+1, cap);

            // 11. Call c(y) and return its results
            debug("charSetMatcher: attempting completion\n");
            var ret = com(y, vars);
            debug("charSetMatcher: completion returned: " + ret + "\n");
            return ret;
        };
        return matcher;
    };

    // 3. Call CharacterSetMatcher(a, false) and return its Matcher result.
    return new Token(Token.ATOM, characterSetMatcher(a, false));
};

Parser.disj_alt_bar_dot_disj.def = "red_alternative_empty";
Parser.disj_alt_bar_dot_disj[Token.DISJUNCTION] = Parser.disj_alt_bar_disj_dot;
Parser.disj_alt_bar_dot_disj[Token.ALTERNATIVE] = Parser.alternative_dot;

Parser.alternative_term_dot.def = "red_alternative_alternative_term";
Parser.prototype.red_alternative_alternative_term = function()
{
    // Alternative : Alternative Term
    // Ecma 15.10.2.4
    // 1. Evaluate alternative to obtain a matcher m1
    // 2. Evaluate term to obtain a Matcher m2
    var m2 = this.stack.top().value;
    this.stack.pop();
    var m1 = this.stack.top().value;
    this.stack.pop();

    // 3. Return an internal matcher closure that takes two args, a State x,
    // and a continuation c, and performs the following:
    var matcher = function(x, c, vars)
    {
        // 1. Create a continuation d that takes a state argument y and returns
        // the result of calling m2(y, c)
        var d = function(y, vars)
        {
            debug("attempting term matcher\n");
            return m2(y, c, vars);
        };
        // 2. Call m1(x, d) and return its result
        debug("attempting alternative-term matcher\n");
        debug("(input is:" + vars.input + ")\n");
        return m1(x, d, vars);
    };
    return new Token(Token.ALTERNATIVE, matcher);
};

Parser.atom_dot.def = "red_term_atom";
Parser.prototype.red_term_atom = function()
{
    // Term : Atom
    // Ecma 15.10.2.5
    // The production Term :: Atom evaluates by evaluating Atom to obtain
    // a Matcher and returning that matcher.
    var value = this.stack.top().value;
    this.stack.pop();
    return new Token(Token.TERM, value);
};

Parser.disj_alt_bar_disj_dot.def = "red_disj_alt_bar_disj";
Parser.prototype.red_disj_alt_bar_disj = function()
{
    // Disjunction: Alternative '|' Disjunction
    // Ecma 15.10.2.3
    // 1. Evaluate alternative to obtain a Matcher m1
    // 2. Evaluate disjunction to obtain a Matcher m2
    var m2 = this.stack.top().value;
    this.stack.pop();
    this.stack.pop();
    var m1 = this.stack.top().value;
    this.stack.pop();

    // 3. Return an internal matcher closure that takes two arguments, a
    // State x and a Continuation c, and performs the following
    var matcher = function(x, c, vars)
    {
        // 1. Call m1(x, c) and let r be its result
        var r = m1(x, c, vars);

        // 2. if r isn't failure, return r
        if (r != State.FAILURE)
        {
            return r;
        }

        // 3. Call m2(x,c) and return its result
        return m2(x, c, vars);
    };
    return new Token(Token.DISJUNCTION, matcher);
};

Parser.accepted.accepted = true;

var State = function(endIndex, captures)
{
    this.endIndex = endIndex;
    this.captures = captures;
};

State.prototype.valueOf = function()
{
    return "(" + this.endIndex + ", " + this.captures + ")";
};

State.FAILURE = -1;

// CharSet([char1,[char2,[...]]]);
var CharSet = function()
{
    // A CharSet is a mathematical set of characters.
    // We'll use the objects hash table. A character is in
    // the set if this[char] == true;
    for (var i = 0; i < arguments.length; i++)
    {
        this[arguments[i]] = true;
    }
};



//---------------------------------------------------------------------//
Esiply.set_attributes(this, "RegExp", Esiply.DONT_ENUM);
RegExp = Esiply.create_janus_function(

// Ecma 15.10.3.1 RegExp(pattern, flags)
function(pattern, flags)
{
    // If pattern is an object R whose [[class]] property is "RegExp" and
    // flags is undefined, then return R unchanged.
    if (typeof pattern == "object"
        && Esiply.get_class(pattern) == "RegExp"
        && typeof flags == "undefined")
    {
        return pattern;
    }

    // Otherwise call the RegExp constructor, passing it the pattern
    // and flags, and return that
    return new RegExp(pattern, flags);
},

// Ecma 15.10.4.1 new RegExp(pattern, flags)
function(pattern, flags)
{
    debug("RegExp: pattern: " + pattern + "\n");
    debug("RegExp: flags: " + flags + "\n");
    // TODO: If pattern is an object R whose [[class]] property is "RegExp" and 
    // flags is undefined, then let p be the pattern used to construct R and
    // let F be the flags used to construct r.

    // TODO: If pattern is an object R whose [[class]] property is "RegEx" 
    // and flags is not undefined, then throw a TypeError exception.

    // Let p be the empty string if pattern is undefined and toString(pattern)
    // otherwise
    var p = typeof pattern == "undefined" ? "" : String(pattern);

    // Let f be the empty string if flags is undefined and toString flags
    // otherwise
    var f = typeof flags == "undefined" ? "" : String(flags);

    var obj = {};

    // The global property of the newly constructed object is set to a
    // Boolean value that is true if F contains the character "g" and false
    // otherwise
    // The ignoreCase property of the newly constructed object is set
    // to a Boolean value that is true if F contains the character "i" and
    // false otherwise
    // The multiline property of the newly constructed object is set
    // to a Boolean value that is true if f contains the character "m" and
    // false otherwise
    // if f contains any character other than "g", "i", or "m", or
    // if it contains the same one more than once, then throw a SyntaxError
    // exception.
    obj.global = false;
    obj.ignoreCase = false;
    obj.multiline = false;
    for (var i = 0; i < flags.length; i++)
    {
        if (!obj.global && flags.charAt(i) == "g")
        {
            obj.global = true;
        }
        else if (!obj.ignoreCase && flags.charAt(i) == "i")
        {
            obj.ignoreCase = true;
        }
        else if (!obj.multiline && flags.charAt(i) == "m")
        {
            obj.multiline = true;
        }
        else
        {
            throw new SyntaxError("Invalid or duplicate RegExp flag"
                    + flags.charAt(i));
        }
    }

    var parser = new Parser(new Lexer(p));
    var match = parser.parse();
    if (typeof match == "undefined")
    {
        throw new SyntaxError("Syntax error in RegExp: " + pattern);
    }

    // TODO: match should be [[match]]
    obj.match = match;

    // The source property of the newly constructed object is set to an
    // implementation-defined string value in the form of a Pattern based
    // on p.
    obj.source = p;

    // The lastIndex property of the newly constructed object is set to 0
    obj.lastIndex = 0;

    // The [[prototype]] property of the newly constructed object is set
    // to the original RegExp prototype object
    Esiply.set_prototype(obj, RegExp.prototype);

    // The [[class]] property is "RegExp"
    Esiply.set_class(obj, "RegExp");
    return obj;
});

// Ecma 15.10.5.1 RegExp.prototype
// The initial value of RegExp.prototype is the RegExp prototype object
RegExp.prototype = {};
Esiply.set_attributes(RegExp, "prototype",
        Esiply.DONT_ENUM | Esiply.DONT_DELETE | Esiply.READ_ONLY);

// Ecma 15.10.6.1 RegExp.prototype.constructor
Esiply.set_attributes(RegExp.prototype, "constructor", Esiply.DONT_ENUM);
RegExp.prototype.constructor = RegExp;

// Ecma 15.10.6.2 RegExp.prototype.exec(string)
// Performance a regular expression match of string against the regular
// expression and returns an Array object containing the results of the
// match, or null if the string did not match.
Esiply.set_attributes(RegExp.prototype, "exec", Esiply.DONT_ENUM);
RegExp.prototype.exec = function(string)
{
    // 1. Let s be the value of toString(string)
    var s = String(string);

    // 2. Let length be the length of s
    var length = s.length;

    // 3. Let lastIndex be the value of the lastIndex property
    var lastIndex = this.lastIndex;

    // 4. Let i be the value of tointeger(lastIndex)
    // 5. If the global property is false, let i = 0
    var i = this.global ? Math.floor(lastIndex) : 0;

    // 6. If i < 0 or i > length then set lastIndex to 0 and return null
    var r = State.FAILURE;
    while (true)
    {
        if (i < 0 || i > length)
        {
            this.lastIndex = 0;
            return null;
        }

        // 7. Call [[match]], giving it the arguments s and i.
        // if failure is returned, go to step 8, otherwise let r
        // be its state result and go to step 10.
        r = this.match(s, i);
        if (r != State.FAILURE)
        {
            break;
        }

        // 8. let i = i + 1;
        // 9. go to step 6
        i++;
    }

    // 10. let e be r's endIndex value
    var e = r.endIndex;

    // 11. if the global property is true, set lastIndex to e
    if (this.global)
    {
        this.lastIndex = e;
    }

    // 12. Let n be the length of r's captures array
    // TODO: captures starts at index 1, right?
    var n = r.captures.length - 1;

    // 13. Return a new array with the following properties:
    var ret = new Array();

    // The index property is set to the position of the matched substring
    // within the complete string s.
    ret.index = i;

    // The input property is set to s
    ret.input = s;

    // The length property is set to n+1
    ret.length = n + 1;

    // The 0 property is set to the matched substring
    ret[0] = s.substring(i, e);

    // for each integer i such that i > 0 and i <= n, set the property
    // named toString(i) to the ith element of r's captures array
    for (var i = 1; i <= n; i++)
    {
        ret[i] = r.captures[i];
    }
    return ret;
};

// Ecma 15.10.6.3 RegExp.prototype.test(string)
// Equivalent to the expression RegExp.prototype.exec(string) != null;
Esiply.set_attributes(RegExp.prototype, "test", Esiply.DONT_ENUM);
RegExp.prototype.test = function(string)
{
    return this.exec(string) != null;
};

// Ecma 15.10.6.3 RegExp.prototype.toString()
// toString returns a string value formed by concatenating the strings "/",
// src, and "/"; plus "g" if the global propery is true, "i" if the 
// ignoreCase property is true, and "m" if the multiline property is true.
// Where src is a string in the form of a Pattern representing the current
// regular expression.
Esiply.set_attributes(RegExp.prototype, "toString", Esiply.DONT_ENUM);
RegExp.prototype.toString = function()
{
    var flags = this.global ? "g" : "";
    flags += this.ignoreCase ? "i" : "";
    flags += this.multiline ? " m" : "";

    return "/" + this.source + "/" + flags;
};

